Conversión de Notación Posfija a Prefija

Objetivo

Tu objetivo es convertir una expresión posfija (Notación Polaca Inversa) en su equivalente expresión prefija (Notación Polaca) mediante la construcción y recorrido de un árbol de expresión.

Algoritmo

1. Construye el Árbol de Expresión: Procesa la expresión posfija de izquierda a derecha utilizando una pila.
   • Cuando se encuentra un operando (por ejemplo, A, B), crea un árbol con un solo nodo para él y colócalo en la pila.
   • Cuando se encuentra un operador (por ejemplo, +, *) se encuentra, extrae dos árboles de la pila. El primero extraído es el hijo derecho (T₂) y el segundo es el hijo izquierdo (T₁). Crea un nuevo árbol con el operador como raíz y vuelve a colocarlo en la pila.
2. Genera la Cadena Prefija: Después de procesar todos los tokens, la pila contendrá el árbol de expresión completo. Realiza un recorrido en preorden (Raíz → Izquierda → Derecha) sobre este árbol para producir la expresión prefija final.

Ejemplo

Para la expresión posfija A B + C *, el algoritmo construye el siguiente árbol:

  *
   / \
  +   C
 / \
A   B

Un recorrido en preorden produce la expresión prefija: * + A B C.

Formato Entrada/Salida

Entrada

• Línea 1: Un entero N (1 ≤ N ≤ 1000), el número de tokens.
• Línea 2: La expresión posfija, con N tokens separados por espacios.

Reglas de Tokens

• Operandos: Letras mayúsculas únicas (A-Z).
• Operadores: Los cuatro operadores binarios: +, -, *, /.

Salida

• Una sola línea que contiene la expresión prefija correspondiente, con tokens separados por espacios.

Ejemplos

Ejemplo 1:

5

A B + C *

* + A B C

Ejemplo 2:

7

A B C * + D /

/ + A * B C D

Ejemplo 3:

7

A B + C D - *

* + A B - C D

Limitaciones